#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:
    deque<ListNode *> Que;
    void reorderList(ListNode *head)
    {
        ListNode *ptr = head, *_hot = nullptr;
        for (int i = 0; ptr != nullptr; ++i, ptr = ptr->next)
        {
            Que.emplace_back(ptr);
        }
        for (int i = 0; Que.empty() == false; ++i)
        {
            if (i % 2 == 0)
            {
                ptr = Que.front();
                Que.pop_front();
            }
            else
            {
                ptr = Que.back();
                Que.pop_back();
            }
            if (ptr != head)
                _hot->next = ptr;
            _hot = ptr;
            _hot->next = nullptr;
        }
        return;
    }
};